package main

import (
	"container/list"
	"fmt"
)

func isEvenOddTree(root *TreeNode) bool {
	queue := list.New()
	queue.PushBack(root)
	var level = 1
	for queue.Len() > 0 {
		var size = queue.Len()
		var pre *TreeNode = nil
		for i := 0; i < size; i++ {
			curTree := queue.Remove(queue.Front()).(*TreeNode)
			if curTree.Val%2 != level%2 {
				return false
			}
			if pre == nil {
				pre = curTree
			} else {
				if level%2 == 1 && pre.Val >= curTree.Val {
					return false
				}
				if level%2 == 0 && pre.Val <= curTree.Val {
					return false
				}
				pre = curTree
			}
			if nil != curTree.Left {
				queue.PushBack(curTree.Left)
			}
			if nil != curTree.Right {
				queue.PushBack(curTree.Right)
			}
		}
		level++
	}
	return true
}

func main() {
	l1l := TreeNode{
		nil, nil, 10,
	}
	l1r := TreeNode{
		nil, nil, 4,
	}
	root := TreeNode{
		&l1l, &l1r, 1,
	}
	fmt.Println(isEvenOddTree(&root))
}
